import org.junit.jupiter.api.Test;

import java.util.Arrays;

public class _34_在排序数组中查找元素的第一个和最后一个位置_二分查找第二种写法 {
    @Test
    public void test(){
        int []arr={1,4};
        System.out.println(Arrays.toString(searchRange(arr, 4)));
    }

    /**
     * 二分查找
     * @param nums
     * @param target
     * @return
     */
    public int[] searchRange(int[] nums, int target) {
        if (nums.length==0) return new int[]{-1,-1};
        if (nums.length==1) return target==nums[0]?new int[]{0,0}:new int[]{-1,-1};
        int search = binarySearch(nums, target);
        int left=search;
        int right = search;
        if (left==-1) return new int[]{-1,-1};
        //找出左边界，不只是有两个元素，还可能有多个
        while (left-1>=0&&nums[left-1]==nums[left]) left--;
        //找出右边界，不只是有两个元素，还可能有多个
        while (right+1<=nums.length-1&&nums[right+1]==nums[right]) right++;
        return new int[]{left,right};
    }

    public int binarySearch(int []arr,int target){
        int left=0;
        int right =arr.length-1;
        while (left<=right){
            int mid=left+(right-left)/2;
            if (arr[left]==target)return left;
            if (arr[right]==target)return right;
            if (arr[mid]==target){
                return mid;
            }else if (target<arr[mid]){
                left=left+1;
                right=mid-1;
            }else {
                left=mid+1;
                right=right-1;
            }
        }
        return -1;
    }
}
